package cn.xmoit.other;

import java.math.BigDecimal;
import java.text.DecimalFormat;
import java.util.Arrays;

public class Test {

	/**
	 * 冒泡排序
	 * @param a 数组
	 * @param n 数组大小
	 */
	public void bubbleSort(int[] a, int n) {
		if (n <= 1) {
			return;
		}

		for (int i = 0; i < n; ++i) {
			// 提前退出冒泡循环的标志位
			boolean flag = false;
			for (int j = 0; j < n - i - 1; ++j) {
				// 交换
				if (a[j] > a[j + 1]) {
					int tmp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = tmp;
					// 表示有数据交换
					flag = true;
				}
			}
			// 没有数据交换，提前退出
			if (!flag) {
				break;
			}
		}
	}

	/**
	 * 插入排序
	 * @param a 数组
	 * @param n 数组大小
	 */
	public static void insertionSort(int[] a, int n) {
		if (n <= 1) {
			return;
		}

		for (int i = 1; i < n; ++i) {
			int value = a[i];
			int j = i - 1;
			// 查找插入的位置
			for (; j >= 0; --j) {
				if (a[j] > value) {
					// 数据移动
					a[j + 1] = a[j];
				}
				else {
					break;
				}
			}
			// 插入数据
			a[j + 1] = value;
		}
	}

	/**
	 * 选择排序
	 * @param a 数组
	 * @param n 数组大小
	 */
	public static void selectSort(int[] a, int n) {
		if (n <= 0) {
			return;
		}
		for (int i = 0; i < n; i++) {
			int min = i;
			for (int j = i; j < n; j++) {
				if (a[j] < a[min]) {
					min = j;
				}
			}
			if (min != i) {
				int temp = a[i];
				a[i] = a[min];
				a[min] = temp;
			}
		}
	}

	/**
	 * 归并排序
	 * @param a 数组
	 * @param n 数组大小
	 */
	public static void mergeSort(int[] a, int n) {
		if (n < 1) {
			return;
		}
		mergeSorting(a, 0, n - 1);
	}

	/**
	 * 归并排序调用，分解为若干个子问题
	 * @param a 数组
	 * @param start 起始位置
	 * @param end 截止位置
	 */
	private static void mergeSorting(int[] a, int start, int end) {
		if (start >= end) {
			return;
		}
		int mid = (start + end) / 2;
		mergeSorting(a, start, mid);
		mergeSorting(a, mid + 1, end);
		merge(a, start, mid, end);
	}

	/**
	 * 归并排序数据合并
	 * @param a 数组
	 * @param start 起始位置
	 * @param mid 中心位置
	 * @param end 截止位置
	 */
	private static void merge(int[] a, int start, int mid, int end) {
		int[] temp = new int[end - start + 1];
		int k = 0;
		int left = start;
		int right = mid + 1;
		while (left <= mid && right <= end) {
			if (a[left] <= a[right]) {
				temp[k++] = a[left++];
			}
			else {
				temp[k++] = a[right++];
			}
		}
		int restStartIndex = left;
		int restEndIndex = mid;
		if (right <= end) {
			restStartIndex = right;
			restEndIndex = end;
		}
		while (restStartIndex <= restEndIndex) {
			temp[k++] = a[restStartIndex++];
		}
		if (end - start + 1 >= 0) {
			System.arraycopy(temp, 0, a, start, end - start + 1);
		}
	}

	/**
	 * 快速排序
	 * @param a 数组
	 * @param n 数组大小
	 */
	public static void quickSort(int[] a, int n) {
		if (n < 1) {
			return;
		}
		quickSorting(a, 0, n - 1);
	}

	/**
	 * 快速排序调用，分解成若干个分区
	 * @param a 数组
	 * @param start 起始位置
	 * @param end 截止位置
	 */
	private static void quickSorting(int[] a, int start, int end) {
		if (start >= end) {
			return;
		}
		int position = partition(a, start, end);
		quickSorting(a, start, position - 1);
		quickSorting(a, position + 1, end);
	}

	/**
	 * 快速排序分区方法
	 * @param a 数组
	 * @param start 起始位置
	 * @param end 截止位置
	 * @return 位置
	 */
	private static int partition(int[] a, int start, int end) {
		int pivot = a[end];
		int left = start;
		for (int i = start; i < end; i++) {
			if (a[i] < pivot) {
				int temp = a[left];
				a[left++] = a[i];
				a[i] = temp;
			}
		}
		int temp = a[left];
		a[left] = pivot;
		a[end] = temp;
		return left;
	}

	/**
	 * 基数排序
	 * @param arr 数组
	 * @param number 桶数量
	 */
	public static void radixSort(int[] arr, int number) {
		// 获取最大值
		int max = 0;
		for (int value : arr) {
			if (value > max) {
				max = value;
			}
		}
		// 获取最大值的位数
		int maxLength = ("" + max).length();
		// 存放桶数据
		int[][] bucket = new int[number][arr.length];
		// 每个桶位置的数量统计
		int[] bucketCounts = new int[number];
		// 循环按位排序
		for (int j = 0, n = 1; j < maxLength; j++, n = n * number) {
			// 计算数据应该存放到哪个桶位置
			for (int i : arr) {
				int location = i / n % number;
				bucket[location][bucketCounts[location]] = i;
				bucketCounts[location]++;
			}

			// 取出最新的桶数据，重新放置到原数组中
			int port = 0;
			for (int k = 0; k < number; k++) {
				if (bucketCounts[k] != 0) {
					for (int l = 0; l < bucketCounts[k]; l++) {
						arr[port] = bucket[k][l];
						port++;
					}
					bucketCounts[k] = 0;
				}
			}
			int toString = j + 1;
			System.out.println("第" + toString + "次排序的结果是" + Arrays.toString(arr));
		}
	}

	/**
	 * 计数排序
	 * @param arr 要排序的数组大小
	 * @param n 数组元素个数
	 */
	public static void countingSort(int[] arr, int n) {
		if (n <= 1) {
			return;
		}

		// 默认数组最大的元素为数组第一个元素
		int max = arr[0];
		// 遍历数组的所有的元素，找到最大的元素
		for (int i = 1; i < n; i++) {
			// 若后面的元素大于指定的数组元素，则把元素进行交换
			if (arr[i] > max) {
				max = arr[i];
			}
		}

		// 申请一个计数数组，下标从0~max。
		int[] c = new int[max + 1];

		// 遍历数组，将每个元素的个数放入到计数数组中，比如分数为0的元素，在c[0]就累加1，依次类推
		for (int i = 0; i < n; i++) {
			c[arr[i]]++;
		}

		// 开始重新整理c[]数组，将c[]数组顺序求和，比如分数0的个数1，分数为1的个数为3。那么重新整理后，分数<=0的为1，分数<=1人数诶1+3=4个，因为包含了<=0的个数，依次类推
		// 所以终止条件为i<=max
		for (int i = 1; i <= max; i++) {
			c[i] = c[i] + c[i - 1];
		}

		// 这时候开始进行排序，创建一个跟要排序的数组一样大小的数据空间
		int[] temp = new int[n];

		// 开始循环需要排序的数据
		for (int i = 0; i < n; i++) {
			// 计算出需要往temp临时数组哪个索引位置存放arr[i]的值。
			// 根据原始数组的值找到计数数组的对应值的计数个数，得到c[arr[i]]的值，也就是temp数组从0开始，所以需要减一
			int index = c[arr[i]] - 1;
			temp[index] = arr[i];
			// 每次循环，计数数组的元素值减一，因为数组放到了temp数组中
			c[arr[i]]--;
		}

		// 重新赋值
		System.arraycopy(temp, 0, arr, 0, n);
	}

	public int binarySearch(int[] a, int val) {
		return binarySearchInternally(a, 0, a.length - 1, val);
	}

	private int binarySearchInternally(int[] a, int start, int end, int val) {
		if (start > end) {
			return -1;
		}
		int mid = start + ((end - start) >> 1);
		if (a[mid] == val) {
			return mid;
		}
		else if (a[mid] > val) {
			end = mid - 1;
			return binarySearchInternally(a, mid + 1, end, val);
		}
		else {
			start = mid + 1;
			return binarySearchInternally(a, start, mid - 1, val);
		}
	}

	/**
	 * 求一个数的平方根，并保留指定精度
	 * @param n 给定数字，支持任意正数
	 * @param precision 保留精度
	 * @return 计算结果
	 */
	public static double sqrt(double n, int precision) {
		if (n < 0) {
			return Double.NaN;
		}

		double low = 0;
		double high = n;
		double ret = 0;

		// 保留 precision 位小数
		StringBuilder sb = new StringBuilder("0.");
		for (int i = 0; i < precision; i++) {
			sb.append("0");
		}
		DecimalFormat df = new DecimalFormat(sb.toString());

		// 计算整数位和小数位，并考虑到四舍五入
		for (int i = 0; i < precision + 2; i++) {
			if (i > 0) {
				low = 1;
				high = 9;
			}
			while (low <= high) {
				double mid = (low + high) / 2;
				double tmp = BigDecimal.valueOf(ret).add(BigDecimal.valueOf(mid * Math.pow(10, -i))).doubleValue();
				if (Math.pow(tmp, 2) == n) {
					return Double.parseDouble(df.format(tmp));
				}
				else if (Math.pow(tmp, 2) < n) {
					low = mid + 1;
				}
				else {
					high = mid - 1;
				}
			}

			ret += high * Math.pow(10, -i);
		}

		return Double.parseDouble(df.format(ret));
	}

	public static int bsearch(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (a[mid] >= value) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}

		if (low < n && a[low] == value) {
			return low;
		}
		else {
			return -1;
		}
	}

	public static int bsearch2(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (a[mid] > value) {
				high = mid - 1;
			}
			else if (a[mid] < value) {
				low = mid + 1;
			}
			else {
				if ((mid == 0) || (a[mid - 1] != value)) {
					return mid;
				}
				else {
					high = mid - 1;
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] ints = { 1, 3, 4, 5, 6, 8, 8, 8, 11, 18 };
		System.out.println(bsearch2(ints, 10, 8));
		// System.out.println(Arrays.toString(ints));
	}

}
